{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rearrange Array to Maximize Prefix Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #prefix-sum #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #前缀和 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重排数组以得到最大前缀分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 。你可以将 <code>nums</code> 中的元素按 <strong>任意顺序</strong> 重排（包括给定顺序）。</p>\n",
    "\n",
    "<p>令 <code>prefix</code> 为一个数组，它包含了 <code>nums</code> 重新排列后的前缀和。换句话说，<code>prefix[i]</code> 是 <code>nums</code> 重新排列后下标从 <code>0</code> 到 <code>i</code> 的元素之和。<code>nums</code> 的 <strong>分数</strong> 是 <code>prefix</code> 数组中正整数的个数。</p>\n",
    "\n",
    "<p>返回可以得到的最大分数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,-1,0,1,-3,3,-3]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>数组重排为 nums = [2,3,1,-1,-3,0,-3] 。\n",
    "prefix = [2,5,6,5,2,2,-1] ，分数为 6 。\n",
    "可以证明 6 是能够得到的最大分数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [-2,-3,0]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不管怎么重排数组得到的分数都是 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>6</sup> &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rearrange-array-to-maximize-prefix-score](https://leetcode.cn/problems/rearrange-array-to-maximize-prefix-score/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rearrange-array-to-maximize-prefix-score](https://leetcode.cn/problems/rearrange-array-to-maximize-prefix-score/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,-1,0,1,-3,3,-3]', '[-2,-3,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        # ans 为历史最大值的下标\n",
    "        ans = [0]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        # ans 为历史最大值的下标\n",
    "        ans = [0]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        a=b=sum(nums)\n",
    "        ans =[0]\n",
    "        for i,v in enumerate(nums,1):\n",
    "            if v:\n",
    "                a-=1\n",
    "            else:\n",
    "                a+=1\n",
    "                if a>b:\n",
    "                    ans=[i]\n",
    "                    b=a\n",
    "                elif a==b:\n",
    "                    ans.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        right = nums.count(1)\n",
    "        mx = right\n",
    "        ans = [0]\n",
    "        left = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            left += x ^ 1\n",
    "            right -= x & 1\n",
    "            if left + right == mx:\n",
    "                ans.append(i + 1)\n",
    "            elif left + right > mx:\n",
    "                ans = [i + 1]\n",
    "                mx = left + right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        res = [0]\n",
    "        l = 0\n",
    "        r = nums.count(1)\n",
    "        m = l + r\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "            if l+r == m:\n",
    "                res.append(i+1)\n",
    "            elif l+r >m:\n",
    "                res = [i+1]\n",
    "                m = l + r \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        # ans 为历史最大值的下标\n",
    "        ans = [0]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        maxscore = 0\n",
    "        presum = 0\n",
    "        ret = [0]\n",
    "\n",
    "        for i,num in enumerate(nums) :\n",
    "            if num == 0 :\n",
    "                presum += 1\n",
    "                if presum > maxscore :\n",
    "                    maxscore = presum\n",
    "                    ret = [i+1]\n",
    "                elif presum == maxscore :\n",
    "                    ret.append(i+1)\n",
    "            else :\n",
    "                presum -= 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        best = base = sum(nums)\n",
    "        ans = [0]\n",
    "        for i, j in enumerate(nums):\n",
    "            if j:\n",
    "                base -= 1\n",
    "            else:\n",
    "                base += 1\n",
    "                if base > best:\n",
    "                    best = base\n",
    "                    ans = [i + 1]\n",
    "                elif base == best:\n",
    "                    ans.append(i + 1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        pres = best = 0\n",
    "        ans = [0]\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                pres += 1\n",
    "                if pres > best:\n",
    "                    best = pres\n",
    "                    ans = [i+1]\n",
    "                elif pres == best:\n",
    "                    ans.append(i+1)\n",
    "            else:\n",
    "                pres -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        # ans 为历史最大值的下标\n",
    "        ans = [0]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        # ans 为历史最大值的下标\n",
    "        ans = [0]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "                # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        ans = [0]\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        presum, m, ans = 0, -inf, []\n",
    "        for i in range(n+1):\n",
    "            if (res:= presum * 2 - i) > m:\n",
    "                m = res\n",
    "                ans = [i]\n",
    "            elif res == m:\n",
    "                ans.append(i)\n",
    "            if i < n:\n",
    "                presum += nums[i] == 0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        mx = score = sum(nums)\n",
    "        ans = [0]\n",
    "        for i in range(1, len(nums)+1):\n",
    "            score += 1 - 2 * nums[i-1]\n",
    "            if score > mx:\n",
    "                mx = score\n",
    "                ans = [i]\n",
    "            elif mx == score:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        presum = best = 0\n",
    "        ans=[0]\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i+1]\n",
    "                elif presum == best:\n",
    "                    ans. append(i+1)\n",
    "            else :\n",
    "                presum -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        cnt=Counter(nums)\n",
    "        cnt0=cnt[0]\n",
    "        cnt1=cnt[1]\n",
    "        ma=cnt1\n",
    "        cur=cnt1\n",
    "        for x in nums:\n",
    "            if x==0:\n",
    "                cur+=1\n",
    "            else:\n",
    "                cur-=1\n",
    "            ma=max(ma,cur)\n",
    "        ans=[]\n",
    "        cur=cnt1\n",
    "        if cur==ma:\n",
    "            ans.append(0)\n",
    "        for i,x in enumerate(nums):\n",
    "            if x==0:\n",
    "                cur+=1\n",
    "            else:\n",
    "                cur-=1\n",
    "            if cur==ma:\n",
    "                ans.append(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        pres = best = 0\n",
    "        ans = [0]\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                pres += 1\n",
    "                if pres > best:\n",
    "                    best = pres\n",
    "                    ans = [i+1]\n",
    "                elif pres == best:\n",
    "                    ans.append(i+1)\n",
    "            else:\n",
    "                pres -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        presum, m, ans = 0, -inf, []\n",
    "        for i in range(n+1):\n",
    "            if (res:= presum * 2 - i) > m:\n",
    "                m = res\n",
    "                ans = [i]\n",
    "            elif res == m:\n",
    "                ans.append(i)\n",
    "            if i < n:\n",
    "                presum += nums[i] == 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        presum, m, ans = 0, -inf, []\n",
    "        for i in range(n+1):\n",
    "            if (res:= presum * 2 - i) > m:\n",
    "                m = res\n",
    "                ans = [i]\n",
    "            elif res == m:\n",
    "                ans.append(i)\n",
    "            if i < n:\n",
    "                presum += nums[i] == 0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        res = sum(nums)\n",
    "        l,r = 0,res\n",
    "        for idx,i in enumerate(nums):\n",
    "            if i == 0:\n",
    "                l += 1\n",
    "                res = max(res,l+r)\n",
    "            else:\n",
    "                r -= 1\n",
    "                res = max(res,l+r)\n",
    "        l,r = 0,sum(nums)\n",
    "        Res = []\n",
    "        if r == res:\n",
    "            Res.append(0)\n",
    "        for idx,i in enumerate(nums):\n",
    "            if i == 0:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "            if l+r == res:Res.append(idx+1)\n",
    "        return Res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0]\n",
    "        s = sum(nums)\n",
    "        mx = s\n",
    "        c0, c1 = 0, 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == 0:\n",
    "                c0 += 1\n",
    "            else:\n",
    "                c1 += 1\n",
    "            score = c0 + s - c1\n",
    "            #print(f'score = {score}, s = {s}')\n",
    "            if score > mx:\n",
    "                ans = [i + 1]\n",
    "                mx = score\n",
    "            elif score == mx:\n",
    "                ans.append(i + 1)\n",
    "        return ans                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ones_total = sum(nums)\n",
    "        ones_cnt = 0\n",
    "        zeros_cnt = 0\n",
    "        score = ones_total\n",
    "        result = [0]\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 0):\n",
    "                zeros_cnt += 1\n",
    "            else:\n",
    "                ones_cnt += 1\n",
    "            if(score < zeros_cnt + ones_total - ones_cnt):\n",
    "                result = [i+1]\n",
    "                score = zeros_cnt + ones_total - ones_cnt\n",
    "            elif(score == zeros_cnt + ones_total - ones_cnt):\n",
    "                result.append(i+1)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        targat=[]\n",
    "        max_score,current_score=0,0\n",
    "        nums_len=len(nums)\n",
    "        for num in nums:\n",
    "            if num==1:\n",
    "                max_score+=1\n",
    "        targat.append(0)\n",
    "        current_score=max_score\n",
    "        for i in range(1,nums_len+1):\n",
    "            if nums[i-1]==0:\n",
    "                current_score=current_score+1\n",
    "            elif nums[i-1]==1:\n",
    "                current_score=current_score-1\n",
    "\n",
    "            if max_score<current_score:\n",
    "                # print('小于')\n",
    "                # print(i)\n",
    "                targat=[i]\n",
    "                max_score=current_score\n",
    "\n",
    "            elif max_score==current_score:\n",
    "                # print('等于')\n",
    "                # print(i)\n",
    "                targat.append(i)\n",
    "\n",
    "        return targat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ones_total = sum(nums)\n",
    "        ones_cnt = 0\n",
    "        zeros_cnt = 0\n",
    "        score = ones_total\n",
    "        result = [0]\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 0):\n",
    "                zeros_cnt += 1\n",
    "            else:\n",
    "                ones_cnt += 1\n",
    "            if(score < zeros_cnt + ones_total - ones_cnt):\n",
    "                result = [i+1]\n",
    "                score = zeros_cnt + ones_total - ones_cnt\n",
    "            elif(score == zeros_cnt + ones_total - ones_cnt):\n",
    "                result.append(i+1)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ones_total = sum(nums)\n",
    "        ones_cnt = 0\n",
    "        zeros_cnt = 0\n",
    "        score = ones_total\n",
    "        result = [0]\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 0):\n",
    "                zeros_cnt += 1\n",
    "            else:\n",
    "                ones_cnt += 1\n",
    "            if(score < zeros_cnt + ones_total - ones_cnt):\n",
    "                result = [i+1]\n",
    "                score = zeros_cnt + ones_total - ones_cnt\n",
    "            elif(score == zeros_cnt + ones_total - ones_cnt):\n",
    "                result.append(i+1)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        s = sum(nums)\n",
    "        sl, sr = 0, s\n",
    "        ans = [0]\n",
    "        mx = s\n",
    "        for i, x in enumerate(nums):\n",
    "            sl += x ^ 1\n",
    "            sr -= x\n",
    "            score = sl + sr\n",
    "            if score > mx:\n",
    "                mx = score\n",
    "                ans = [i + 1]\n",
    "            elif score == mx:\n",
    "                ans.append(i + 1)\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        res = [0]\n",
    "        l = 0\n",
    "        r = nums.count(1)\n",
    "        m = l + r\n",
    "        for i in range(len(nums)):\n",
    "            print(m)\n",
    "            if nums[i] == 0:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "            if l+r == m:\n",
    "                res.append(i+1)\n",
    "            elif l+r >m:\n",
    "                res = [i+1]\n",
    "                m = l + r \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[0]*(n+1)\n",
    "        total=sum(nums)\n",
    "        ans[0]=total\n",
    "        count_0,count_1=0,total\n",
    "        for i in range(1,n+1):\n",
    "            if nums[i-1]==0:\n",
    "                count_0+=1\n",
    "            else:\n",
    "                count_1-=1\n",
    "            ans[i]=count_0+count_1\n",
    "        ans[n]=nums.count(0)\n",
    "        cur=max(ans)\n",
    "        return [i for i in range(n+1) if ans[i]==cur]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        left = 0\n",
    "        right = nums.count(1)\n",
    "        n = len(nums)\n",
    "        ans = [0] * (n+1)\n",
    "        for i in range(n+1):\n",
    "            ans[i] = left+right\n",
    "            if i < n:\n",
    "                if nums[i] == 0:\n",
    "                    left += 1\n",
    "                if nums[i] == 1:\n",
    "                    right -= 1\n",
    "        \n",
    "        maxval = max(ans)\n",
    "        return [i for i, x in enumerate(ans) if x == maxval]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "      n = len(nums)\n",
    "      suffix = [0] * (n + 1)\n",
    "\n",
    "      for i in range(n - 1, -1, -1):\n",
    "        suffix[i] = suffix[i + 1] + (nums[i] == 1)\n",
    "      \n",
    "      ans = []\n",
    "      max_ = float('-inf')\n",
    "\n",
    "      left_sum = 0\n",
    "      for i in range(n + 1):\n",
    "        sum_ = left_sum + suffix[i]\n",
    "        if sum_ > max_:\n",
    "          ans = [i]\n",
    "          max_ = sum_\n",
    "        elif sum_ == max_:\n",
    "          ans.append(i)\n",
    "        \n",
    "        if i == n:\n",
    "          break\n",
    "        \n",
    "        left_sum += nums[i] == 0\n",
    "\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ones = sum(nums)\n",
    "        res = [0] * (n + 1)\n",
    "        base = ones \n",
    "        res[0] = base \n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i - 1]:\n",
    "                base -= 1\n",
    "            else:\n",
    "                base += 1\n",
    "            res[i] = base \n",
    "        mx = max(res)\n",
    "        ans = []\n",
    "        for i in range(n + 1):\n",
    "            if res[i] == mx:\n",
    "                ans.append(i)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        left = 0\n",
    "        right = nums.count(1)\n",
    "        n = len(nums)\n",
    "        ans = [0] * (n+1)\n",
    "        for i in range(n+1):\n",
    "            ans[i] = left+right\n",
    "            if i < n:\n",
    "                if nums[i] == 0:\n",
    "                    left += 1\n",
    "                if nums[i] == 1:\n",
    "                    right -= 1\n",
    "        \n",
    "        maxval = max(ans)\n",
    "        return [i for i, x in enumerate(ans) if x == maxval]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        left=0\n",
    "        right=0\n",
    "        l=len(nums)\n",
    "        for i in range(l):\n",
    "            if nums[i]==1:\n",
    "                right+=1\n",
    "        res.append(left+right)\n",
    "        count=0\n",
    "        while count<l:\n",
    "            if nums[count]==0:\n",
    "                left+=1\n",
    "            if nums[count]==1:\n",
    "                right-=1\n",
    "            res.append(left+right)\n",
    "            count+=1\n",
    "        m=max(res)\n",
    "        ans=[]\n",
    "        for i in range(l+1):\n",
    "            if m==res[i]:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\r\n",
    "        c = collections.Counter(nums)\r\n",
    "        n = len(nums)\r\n",
    "        lf, rt = 0, c[1]\r\n",
    "        ans = [lf + rt]\r\n",
    "        for i in range(n):\r\n",
    "            if nums[i] == 0:\r\n",
    "                lf += 1\r\n",
    "            if nums[i] == 1:\r\n",
    "                rt -= 1\r\n",
    "            ans.append(lf + rt)\r\n",
    "        maxx = max(ans)\r\n",
    "        return [i for i in range(n + 1) if ans[i] == maxx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        sumLeft = 0\n",
    "        sumRight = sum(nums)\n",
    "        scores = []\n",
    "        res = []\n",
    "        mx = 0\n",
    "        for i in range(len(nums)):\n",
    "            scores.append(sumLeft + sumRight)\n",
    "            if scores[i] > mx:\n",
    "                res = [i]\n",
    "                mx = scores[i]\n",
    "            elif scores[i] == mx:\n",
    "                res.append(i)\n",
    "            if nums[i] == 0:\n",
    "                sumLeft += 1\n",
    "            elif nums[i] == 1:\n",
    "                sumRight -= 1\n",
    "        scores.append(sumLeft + sumRight)\n",
    "        if scores[-1] > mx:\n",
    "            res = [len(nums)]\n",
    "        elif scores[-1] == mx:\n",
    "            res.append(len(nums))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        sumLeft = 0\n",
    "        sumRight = sum(nums)\n",
    "        scores = []\n",
    "        res = []\n",
    "        mx = 0\n",
    "        for i in range(len(nums) + 1):\n",
    "            scores.append(sumLeft + sumRight)\n",
    "            if scores[i] > mx:\n",
    "                res = [i]\n",
    "                mx = scores[i]\n",
    "            elif scores[i] == mx:\n",
    "                res.append(i)\n",
    "            if i == len(nums): break\n",
    "            if nums[i] == 0:\n",
    "                sumLeft += 1\n",
    "            elif nums[i] == 1:\n",
    "                sumRight -= 1\n",
    "        scores.append(sumLeft + sumRight)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums)\n",
    "        # 0 - N\n",
    "        zero_nums = [0] * (N+1)\n",
    "        one_nums = [0] * (N+1)\n",
    "\n",
    "        for i in range(1,N+1) :\n",
    "            zero_nums[i] = zero_nums[i-1]\n",
    "            if nums[i-1] == 0 :\n",
    "                zero_nums[i] += 1\n",
    "\n",
    "        for i in range(N-1, -1 , -1) :\n",
    "            one_nums[i] = one_nums[i+1]\n",
    "            if nums[i] == 1 :\n",
    "                one_nums[i] += 1\n",
    "        \n",
    "        ret = []\n",
    "        maxscore = -1\n",
    "        for i in range(N+1) :\n",
    "            score = zero_nums[i] + one_nums[i]\n",
    "            if score > maxscore :\n",
    "                maxscore = score\n",
    "                ret = [i]\n",
    "            elif score == maxscore :\n",
    "                ret.append(i)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left_zeros = [0] * (n + 1)\n",
    "        right_ones = [0] * (n + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            left_zeros[i + 1] = left_zeros[i] + (1 if nums[i] == 0 else 0)\n",
    "            right_ones[n - i - 1] = right_ones[n - i] + (1 if nums[n - i - 1] == 1 else 0)\n",
    "\n",
    "        max_score = 0\n",
    "        max_score_indices = []\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            score = left_zeros[i] + right_ones[i]\n",
    "            if score > max_score:\n",
    "                max_score = score\n",
    "                max_score_indices = [i]\n",
    "            elif score == max_score:\n",
    "                max_score_indices.append(i)\n",
    "\n",
    "        return max_score_indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left, right = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            left[i + 1] = left[i] + (nums[i] == 0)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            right[i] = right[i + 1] + (nums[i] == 1)\n",
    "        cur_max = 0\n",
    "        ans = []\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            res = left[i] + right[i]\n",
    "            if res > cur_max:\n",
    "                cur_max = res\n",
    "                ans = [i]\n",
    "            elif res == cur_max:\n",
    "                ans.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # nums = [0,0,1,0]\n",
    "        prefix = [0] * (len(nums) + 1)\n",
    "        suffix = [0] * (len(nums) + 1)\n",
    "        for i in range(1, len(prefix)):\n",
    "            if nums[i - 1] == 0:\n",
    "                prefix[i] += prefix[i - 1] + 1\n",
    "            else:\n",
    "                prefix[i] = prefix[i - 1]\n",
    "        for i in range(len(suffix) - 2, -1, -1):\n",
    "            if nums[i] == 1:\n",
    "                suffix[i] += suffix[i + 1] + 1\n",
    "            else:\n",
    "                suffix[i] = suffix[i + 1]\n",
    "        res = []\n",
    "        for p, s in zip(prefix, suffix):\n",
    "            res.append(p + s)\n",
    "        maxNum = max(res)\n",
    "        ans = []\n",
    "        for i, v in enumerate(res):\n",
    "            if v == maxNum:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        f = [[0, 0] for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            f[i + 1][0] = f[i][0]\n",
    "            f[i + 1][1] = f[i][1]\n",
    "            f[i + 1][nums[i]] += 1\n",
    "        ret, retlist = f[n][0], [n]\n",
    "        for i in range(n):\n",
    "            if ret == f[i][0] + f[n][1] - f[i][1]:\n",
    "                retlist.append(i)\n",
    "            elif ret < f[i][0] + f[n][1] - f[i][1]:\n",
    "                ret = f[i][0] + f[n][1] - f[i][1]\n",
    "                retlist = [i]\n",
    "        return retlist    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        score = dict()\n",
    "        postsum = sum(nums)\n",
    "        presum = 0\n",
    "        for i in range(len(nums)):\n",
    "            score[i] = i - presum + postsum\n",
    "            presum += nums[i]\n",
    "            postsum -= nums[i]\n",
    "        score[len(nums)] = len(nums) - presum\n",
    "        target = max(score.values())\n",
    "        return [i for i, j in score.items() if j == target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)\n",
    "        res = 0\n",
    "        maxScore = 0\n",
    "        def dfs(x):\n",
    "            nonlocal res, maxScore\n",
    "            size, score = 1, 1\n",
    "\n",
    "            for ch in g[x]:\n",
    "                ch_size = dfs(ch)\n",
    "                score *= ch_size\n",
    "                size += ch_size\n",
    "\n",
    "            # x不是根节点\n",
    "            if x > 0:\n",
    "                score *= n - size\n",
    "\n",
    "            if score > maxScore:\n",
    "                maxScore, res = score, 1\n",
    "            elif score == maxScore:\n",
    "                res += 1\n",
    "\n",
    "            return size\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        children = [[] for _ in range(n)]\n",
    "        for node, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                children[p].append(node)\n",
    "\n",
    "        maxScore, cnt = 0, 0\n",
    "        def dfs(node: int) -> int:\n",
    "            score = 1\n",
    "            size = n - 1\n",
    "            for ch in children[node]:\n",
    "                sz = dfs(ch)\n",
    "                score *= sz\n",
    "                size -= sz\n",
    "            if node != 0:\n",
    "                score *= size\n",
    "            nonlocal maxScore, cnt\n",
    "            if score == maxScore:\n",
    "                cnt += 1\n",
    "            elif score > maxScore:\n",
    "                maxScore, cnt = score, 1\n",
    "            return n - size\n",
    "        dfs(0)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        children = [[] for _ in range(n)]\n",
    "        for node, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                children[p].append(node)\n",
    "\n",
    "        maxScore, cnt = 0, 0\n",
    "        def dfs(node: int) -> int:\n",
    "            score = 1\n",
    "            size = n - 1\n",
    "            for ch in children[node]:\n",
    "                sz = dfs(ch)\n",
    "                score *= sz\n",
    "                size -= sz\n",
    "            if node != 0:\n",
    "                score *= size\n",
    "            nonlocal maxScore, cnt\n",
    "            if score == maxScore:\n",
    "                cnt += 1\n",
    "            elif score > maxScore:\n",
    "                maxScore, cnt = score, 1\n",
    "            return n - size\n",
    "        dfs(0)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "       \n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for w in range(1, n):\n",
    "            v = parents[w]\n",
    "            g[v].append(w)\n",
    "\n",
    "        maxScore = [0]\n",
    "\n",
    "        def dfs(v):\n",
    "            size, score = 1, 1\n",
    "            for w in g[v]:\n",
    "                sz = dfs(w)\n",
    "                size += sz\n",
    "                score *= sz\n",
    "\n",
    "            if v > 0:\n",
    "                score *= n - size\n",
    "\n",
    "            if score > maxScore[0]:\n",
    "                maxScore[0], ans[0] = score, 1\n",
    "            elif score == maxScore[0]:\n",
    "                ans[0] += 1\n",
    "\n",
    "            return size\n",
    "\n",
    "        ans = [0]\n",
    "        dfs(0)\n",
    "        return ans[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHighestScoreNodes(self, parents: List[int]) -> int:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for node, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                g[p].append(node)\n",
    "\n",
    "        maxScore, cnt = 0, 0\n",
    "        def dfs(node: int) -> int:\n",
    "            score = 1\n",
    "            size = n - 1\n",
    "            for ch in g[node]:\n",
    "                sz = dfs(ch)\n",
    "                score *= sz\n",
    "                size -= sz\n",
    "            if node != 0:\n",
    "                score *= size\n",
    "            nonlocal maxScore, cnt\n",
    "            if score == maxScore:\n",
    "                cnt += 1\n",
    "            elif score > maxScore:\n",
    "                maxScore, cnt = score, 1\n",
    "            return n - size\n",
    "        dfs(0)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        num = 0 \n",
    "        prefix = 0\n",
    "        for i in range(len(nums)):\n",
    "            prefix += nums[i]\n",
    "            if nums[i] > 0:\n",
    "                num += 1\n",
    "            else:\n",
    "                if prefix > 0:\n",
    "                    num += 1\n",
    "        return num\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        prefix = nums.sort(reverse = True)\n",
    "        return sum(s>0 for s in accumulate(nums))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(i > 0 for i in accumulate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(s>0 for s in accumulate(nums))\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        pre = 0\n",
    "        rt = 0 \n",
    "        for num in nums:\n",
    "            pre = pre+num \n",
    "            if pre>0:\n",
    "                rt+=1\n",
    "            else:\n",
    "                break \n",
    "        return rt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        s = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            s += x\n",
    "            if s <= 0:\n",
    "                return i\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        cnt = 0\n",
    "        sum = 0\n",
    "        for num in nums:\n",
    "            sum += num\n",
    "            if sum > 0:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        score = 0\n",
    "        prefix_sum = 0\n",
    "        for num in nums:\n",
    "            prefix_sum += num\n",
    "            if prefix_sum > 0:\n",
    "                score += 1\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        ans = 0\n",
    "        ta = 0\n",
    "        for i in nums:\n",
    "            ta+=i\n",
    "            if ta>0:\n",
    "                ans+=1\n",
    "            else:\n",
    "                return ans\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        total=ans=0\n",
    "        for i in nums:\n",
    "            total+=i\n",
    "            if total>0:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.sort(reverse = True)\n",
    "        prefix = 0\n",
    "        for s in nums:\n",
    "            prefix += s\n",
    "            if(prefix > 0):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(x > 0 for x in accumulate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        return sum(s > 0 for s in accumulate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        acc, ans = 0, 0\n",
    "\n",
    "        for num in nums:\n",
    "            acc += num\n",
    "            if acc > 0:\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        count = 0\n",
    "        s = 0\n",
    "        for n in nums:\n",
    "            s += n\n",
    "            if s > 0 :\n",
    "                count += 1\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(s > 0 for s in accumulate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1.先倒叙排序\n",
    "    [2,-1,0,1,-3,3,-3] \n",
    "    ------> [-3,-3,-1,0,1,2,3]\n",
    "    ------> [3,2,1,0,-1,-3,-3]\n",
    "\n",
    "2. return所有大于0的部分\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        cnt = 0\n",
    "        for s in accumulate(nums):\n",
    "            if s > 0 :\n",
    "                cnt+=1\n",
    "        return cnt\n",
    "\n",
    "       \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse= True)\n",
    "        return sum(s > 0 for s in accumulate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1.先倒叙排序\n",
    "    [2,-1,0,1,-3,3,-3] \n",
    "    ------> [-3,-3,-1,0,1,2,3]\n",
    "    ------> [3,2,1,0,-1,-3,-3]\n",
    "\n",
    "2. return所有大于0的部分\n",
    "\n",
    "***注意审题，是大于0的前项和的个数，不是最大的和，也不是非零数量***\n",
    "'''\n",
    "       \n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        cnt = 0\n",
    "        for s in accumulate(nums):\n",
    "            if s > 0 :\n",
    "                cnt+=1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "\n",
    "1.先倒叙排序\n",
    "[2,-1,0,1,-3,3,-3] \n",
    "------> [-3,-3,-1,0,1,2,3]\n",
    "------> [3,2,1,0,-1,-3,-3]\n",
    "\n",
    "2. return 累加 所有大于0的部分\n",
    "\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        cnt = 0\n",
    "        for s in accumulate(nums):\n",
    "            if s > 0 :\n",
    "                cnt+=1\n",
    "        return cnt\n",
    "\n",
    "       \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums = nums[::-1]\n",
    "        count = 0\n",
    "        sum = 0\n",
    "        for i in nums:\n",
    "            sum += i\n",
    "            if sum > 0:\n",
    "                count += 1\n",
    "            else:\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        num = 0 \n",
    "        prefix = 0\n",
    "        for i in range(len(nums)):\n",
    "            prefix += nums[i]\n",
    "            if nums[i] > 0:\n",
    "                num += 1\n",
    "            elif prefix > 0:\n",
    "                num += 1\n",
    "        return num\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        score = 0\n",
    "        prefix_sum = 0\n",
    "        for num in nums:\n",
    "            prefix_sum += num\n",
    "            if prefix_sum > 0:\n",
    "                score += 1\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        if sum(nums) > 0:\n",
    "            return len(nums)\n",
    "        nums.sort(reverse = True)\n",
    "        # print(nums)\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            ans += nums[i]\n",
    "            if ans <= 0:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        score = 0\n",
    "        prefix_sum = 0\n",
    "        for num in nums:\n",
    "            prefix_sum += num\n",
    "            if prefix_sum > 0:\n",
    "                score += 1\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(i > 0 for i in accumulate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        cnt = 0\n",
    "        tmp_sum = 0\n",
    "        for i in nums:\n",
    "            tmp_sum += i\n",
    "            if tmp_sum <= 0:\n",
    "                return cnt\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(s > 0 for s in accumulate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        res=count = 0\n",
    "        nums.sort(reverse = True)\n",
    "        for v in nums:\n",
    "            res += v\n",
    "            if res >0:\n",
    "                count+=1\n",
    "                continue\n",
    "            break\n",
    "        return count\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        ans = 0\n",
    "        ta = 0\n",
    "        for i in nums:\n",
    "            ta+=i\n",
    "            if ta>0:\n",
    "                ans+=1\n",
    "            else:\n",
    "                return ans\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        fs = 0\n",
    "        nums.sort(reverse=True)\n",
    "        x = 0\n",
    "        for i in nums:\n",
    "            x += i\n",
    "            if x > 0:\n",
    "                fs += 1\n",
    "        return fs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        cur_sum = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            cur_sum += num\n",
    "            if cur_sum<=0:\n",
    "                return i\n",
    "        return len(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        res=count = 0\n",
    "        nums.sort(reverse = True)\n",
    "        for v in nums:\n",
    "            res += v\n",
    "            if res >0:\n",
    "                count+=1\n",
    "                continue\n",
    "            break\n",
    "        return count\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        res = 0\n",
    "        add = 0\n",
    "        for i in range(len(nums)):\n",
    "            add += nums[i]\n",
    "            if add > 0:\n",
    "                res += 1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        score = 0\n",
    "        prefix_sum = 0\n",
    "        for num in nums:\n",
    "            prefix_sum += num\n",
    "            if prefix_sum > 0:\n",
    "                score += 1\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        temp_sum=0\n",
    "        count=0\n",
    "        for i in range(len(nums)):\n",
    "            temp_sum+=nums[i]\n",
    "            if temp_sum>0:\n",
    "                count+=1\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def maxScore(self, nums):\n",
    "        score = 0\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(score > 0 for score in accumulate(nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int: \n",
    "        nums = sorted(nums,reverse=True)\n",
    "        ans, res = 0,0\n",
    "        if nums[0] == 0: return 0\n",
    "        for i,num in enumerate(nums):\n",
    "            res += num\n",
    "            if res > 0:\n",
    "                ans+=1\n",
    "            else: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums):\n",
    "        nums.sort(reverse = True)\n",
    "        sumpre = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            sumpre += n\n",
    "            if sumpre <= 0: return i\n",
    "        return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        pre=0\n",
    "        res=0\n",
    "        for num in nums:\n",
    "            pre+=num\n",
    "            if pre>0:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        cur = ans = 0\n",
    "        for num in nums:\n",
    "            cur += num\n",
    "            if cur <= 0:\n",
    "                break\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        ans = 0\n",
    "        ta = 0\n",
    "        for i in nums:\n",
    "            ta+=i\n",
    "            if ta>0:\n",
    "                ans+=1\n",
    "            else:\n",
    "                return ans\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        # return sum([i for i in nums if i>0])\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(s > 0 for s in accumulate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(s > 0 for s in accumulate(nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        score = 0\n",
    "        prefix_sum = 0\n",
    "        for num in nums:\n",
    "            prefix_sum += num\n",
    "            if prefix_sum > 0:\n",
    "                score += 1\n",
    "            else:\n",
    "                break\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        s = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            s += nums[i]\n",
    "            if s <= 0:\n",
    "                return i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        res=count = 0\n",
    "        nums.sort(reverse = True)\n",
    "        for v in nums:\n",
    "            res += v\n",
    "            if res >0:\n",
    "                count+=1\n",
    "                continue\n",
    "            break\n",
    "        return count\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        ans = 0\n",
    "        ta = 0\n",
    "        for i in nums:\n",
    "            ta+=i\n",
    "            ans+= ta>0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "      nums=sorted(nums,reverse=True)\n",
    "      return sum(i>0 for i in accumulate(nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 排序+贪心\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(s > 0 for s in accumulate(nums))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        score = 0\n",
    "        prefix_sum = 0\n",
    "        for num in nums:\n",
    "            prefix_sum += num\n",
    "            if prefix_sum > 0:\n",
    "                score += 1\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        res=count = 0\n",
    "        nums.sort(reverse = True)\n",
    "        for v in nums:\n",
    "            res += v\n",
    "            if res >0:\n",
    "                count+=1\n",
    "        return count\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int: \n",
    "        nums = sorted(nums, reverse=True)\n",
    "        res = nums[0]\n",
    "        if res <= 0:\n",
    "            return 0\n",
    "        ans = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            res += nums[i]\n",
    "            if (res > 0):\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        '''\n",
    "        cur_sum = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            cur_sum += num\n",
    "            if cur_sum<=0:\n",
    "                return i\n",
    "        return len(nums)\n",
    "        '''\n",
    "        return sum(s > 0 for s in accumulate(nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums_p=[s for s in nums if s>0]\n",
    "        nums_n=[s for s in nums if s<=0]\n",
    "        nums_n.sort(reverse=True)\n",
    "        temp_sum=sum(nums_p)\n",
    "        count=len(nums_p)\n",
    "        for i in range(len(nums_n)):\n",
    "            temp_sum+=nums_n[i]\n",
    "            if temp_sum>0:\n",
    "                count+=1\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        now = 0\n",
    "        res = 0\n",
    "        for v in sorted(nums, reverse=True):\n",
    "            now += v\n",
    "            if now > 0:\n",
    "                res += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def maxScore(self, nums):\n",
    "        cnt = 0\n",
    "        nums.sort(reverse=True)\n",
    "        for score in accumulate(nums):\n",
    "            if score > 0:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums, reverse=True)\n",
    "        s = accumulate(nums)\n",
    "        return sum(1 for x in s if x > 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums_p=[s for s in nums if s>0]\n",
    "        nums_n=[s for s in nums if s<=0]\n",
    "        nums_n.sort(reverse=True)\n",
    "        temp_sum=sum(nums_p)\n",
    "        count=len(nums_p)\n",
    "        for i in range(len(nums_n)):\n",
    "            temp_sum+=nums_n[i]\n",
    "            if temp_sum>0:\n",
    "                count+=1\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums = nums[::-1]\n",
    "        count = 0\n",
    "        sum = 0\n",
    "        for i in nums:\n",
    "            sum += i\n",
    "            if sum > 0:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        # ans = 0\n",
    "        # for num in nums:\n",
    "        #     if num >0:\n",
    "        #         ans+=1\n",
    "        nums_len = len(nums)\n",
    "        nums.sort(reverse=True)\n",
    "        # print(nums)\n",
    "        for i in range(1, nums_len):\n",
    "            nums[i]+=nums[i-1]\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            if num >0:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        return sum(a>0 for a in accumulate(sorted(nums,reverse=True)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        count = 0\n",
    "        temp = 0\n",
    "        print(nums)\n",
    "        for num in nums:\n",
    "            if temp > 0:\n",
    "                count += 1\n",
    "            temp += num\n",
    "        if temp > 0:\n",
    "            count += 1 \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def maxScore(self, nums):\n",
    "        cnt = 0\n",
    "        nums.sort(reverse=True)\n",
    "        for score in accumulate(nums):\n",
    "            if score > 0:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                break\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        return sum(s > 0 for s in accumulate(sorted(nums, reverse=True)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        res=count = 0\n",
    "        nums.sort(reverse = True)\n",
    "        print(nums)\n",
    "        for v in nums:\n",
    "            res += v\n",
    "            if res >0:\n",
    "                count+=1\n",
    "        return count\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "      positive_nums = [n for n in nums if n > 0]\n",
    "      negative_nums = [n for n in nums if n <= 0]\n",
    "      score = len(positive_nums)\n",
    "      sum_val = sum(positive_nums)\n",
    "      negative_nums = sorted(negative_nums, reverse=True)\n",
    "      i = 0\n",
    "      while sum_val > 0 and i < len(negative_nums):\n",
    "        sum_val += negative_nums[i]\n",
    "        i += 1\n",
    "        if sum_val > 0:\n",
    "          score += 1\n",
    "      \n",
    "      return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(key = lambda x: -x)\n",
    "        s = 0\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < len(nums) and s >= 0:\n",
    "            s += nums[i]\n",
    "            i += 1\n",
    "            if s > 0:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        new_num = list(accumulate(nums))\n",
    "        return sum(s>0 for s in new_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        sorted_nums = sorted(nums, reverse = True)\n",
    "        prefix = [0 for i in range(len(nums))]\n",
    "        prefix[0] = sorted_nums[0]\n",
    "        cnt = 0\n",
    "        if prefix[0] > 0:\n",
    "            cnt = 1\n",
    "        else:\n",
    "            return 0\n",
    "        for i in range(1,len(nums)):\n",
    "            prefix[i] = prefix[i-1] + sorted_nums[i]\n",
    "            if prefix[i] > 0:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                return cnt\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums) \n",
    "        res = [0] * (n + 1)\n",
    "        ans = 0 \n",
    "        nums.sort(reverse = True) \n",
    "        for i in range(1, n + 1) : \n",
    "            res[i] = res[i - 1] + nums[i - 1]\n",
    "            if res[i] <= 0 : return ans \n",
    "            ans += 1 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        ans = []\n",
    "        count = 0\n",
    "        if nums.count(nums[0]) <= 0:\n",
    "            return 0\n",
    "        for i in accumulate(nums):\n",
    "            ans.append(i)\n",
    "        for i in ans:\n",
    "            if i > 0:\n",
    "                count += 1\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
